package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

  private ArrayList<String> vertexList;//顶点
  private int[][] edges;//图对应的邻接矩阵
  private int numOfEdges;//表示边的数目
  private boolean[] isVisited;//记录顶点是否被访问

  public static void main(String[] args) {
    int n = 8;//5个顶点
//    String vertex[] = {"A","B","C","D","E"};
    String vertex[] = {"1","2","3","4","5","6","7","8"};
//    创建图
    Graph graph = new Graph(n);
//    添加顶点
    for (String ele : vertex) {
      graph.insertVertex(ele);
    }
//    添加边
//    graph.insertEdges(0,1,1);
//    graph.insertEdges(0,2,1);
//    graph.insertEdges(1,2,1);
//    graph.insertEdges(1,3,1);
//    graph.insertEdges(1,4,1);
    graph.insertEdges(0,1,1);
    graph.insertEdges(0,2,1);
    graph.insertEdges(1,3,1);
    graph.insertEdges(1,4,1);
    graph.insertEdges(3,7,1);
    graph.insertEdges(4,7,1);
    graph.insertEdges(2,5,1);
    graph.insertEdges(2,6,1);
    graph.insertEdges(5,6,1);
//    显示图
    graph.show();
//    测试深度优先遍历
    System.out.print("深度优先遍历：");
    graph.dfs();
    System.out.println();
//    测试广度优先遍历
    System.out.print("广度优先遍历：");
    graph.bfs();
  }

  public Graph(int n){
    edges = new int[n][n];
    vertexList = new ArrayList<String>(n);
    numOfEdges = 0;
  }
  public void insertVertex(String vertex){
    vertexList.add(vertex);
  }
  public void insertEdges(int v1,int v2,int weight){
    edges[v1][v2] = weight;
    edges[v2][v1] = weight;
    numOfEdges++;
  }

//  返回节点个数
  public int getNumOfVertex(){
    return vertexList.size();
  }
//  返回边的个数
  public int getNumOfEdges(){
    return numOfEdges;
  }
//  根据下标找到顶点
  public String getValueByIndex(int n){
    return vertexList.get(n);
  }
//  返回权值
  public int getWeight(int v1,int v2){
    return edges[v1][v2];
  }
//  显示图
  public void show(){
    for (int[] edge : edges) {
      System.out.println(Arrays.toString(edge));
    }
  }
//  得到第一个邻接节点的下标
  public int getFirstNeighbor(int index){
    for (int i = 0; i < vertexList.size(); i++) {
      if (edges[index][i] > 0){
        return i;
      }
    }
    return -1;
  }
//  根据前一个邻接节点的下标得到下一个邻接节点
  private int getNextNeighbor(int v1,int v2){
    for (int i = v2 + 1; i < vertexList.size(); i++) {
      if (edges[v1][i] > 0){
        return i;
      }
    }
    return -1;
  }
//  深度优先遍历
  public void dfs(boolean[] isVisited,int i){
//    首先，我们访问该节点，并输出
    System.out.print(getValueByIndex(i) + "->");
//    然后将当前节点标记为已访问，并尝试找他的第一个邻接节点
    isVisited[i] = true;
    int w = getFirstNeighbor(i);
    while (w != -1){//说明有
      if (!isVisited[w]){//没有被访问过
        dfs(isVisited,w);
      }else {
        //如果已经被访问过
        w = getNextNeighbor(i,w);
      }
    }
  }
//  对dfs进行重载，遍历所以顶点
  public void dfs(){
    isVisited = new boolean[vertexList.size()];
    for (int i = 0; i < getNumOfVertex(); i++) {
      if (!isVisited[i]){
        dfs(isVisited,i);
      }
    }
  }
//  广度优先
  public void bfs(boolean[]isVisited,int i){
    int u = 0;
    int w = 0;
    System.out.print(getValueByIndex(i) + "->");
    LinkedList<Integer> list = new LinkedList<>();
    isVisited[i] = true;
    list.addLast(i);

    while (!list.isEmpty()){
//      取出队列头结点的下标
      u = list.removeFirst();
//      得到第一个邻接节点的下标
      w = getFirstNeighbor(i);
      while (w != -1){
        if (!isVisited[w]){
          System.out.print(getValueByIndex(w) + "->");
          isVisited[w] = true;
          list.addLast(w);
        }
        w = getNextNeighbor(u,w);
      }
    }
  }
//  对bfs进行重载，遍历所有顶点
  public void bfs(){
    isVisited = new boolean[vertexList.size()];
    for (int i = 0; i < getNumOfVertex(); i++) {
      if (!isVisited[i]){
        bfs(isVisited,i);
      }
    }
  }
}
